//三角形：https://www.nowcoder.com/practice/2b7995aa4f7949d99674d975489cb7da?tpId=46&tqId=29060&tPage=2&rp=2&ru=/ta/leetcode&qru=/ta/leetcode/question-rankin
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        if (triangle.empty()) 
        {
            return 0;
        }
        // F[i][j], F[0][0]初始化
        vector<vector<int>> min_sum(triangle);
        int line = triangle.size();
        for (int i = 1; i < line; i++) 
        {
            for (int j = 0; j <= i; j++) 
            {
                // 处理左边界和右边界
                if (j == 0) {
                    min_sum[i][j] = min_sum[i - 1][j];
                } else if (j == i) {
                    min_sum[i][j] = min_sum[i - 1][j - 1];
                } else {
                    min_sum[i][j] = min(min_sum[i - 1][j], min_sum[i - 1][j - 1]);
                }
                // F(i,j) = min( F(i-1, j-1), F(i-1, j)) + triangle[i][j]
                min_sum[i][j] = min_sum[i][j] + triangle[i][j];
            }
        }
        int result = min_sum[line - 1][0];
        // min(F(n-1, i))
        for (int i = 1; i < line; i++) {
            result = min(min_sum[line - 1][i], result);
        }
        return result;
    }
};